package search;

import java.util.Arrays;

/**
 * @author yunfei.shang
 * @date 2017/5/27.
 * @descreption 二分查找算法
 */
public class BinarySearch {

    public static int flagIndex = 0;

    public static void main(String[] args) {
        //int times = search(7, dataArray, dataArray.length);
        int length = 10;
        int[] dataArray = fillArray(length);
        //Arrays.sort(dataArray);
        long curTime1 = System.currentTimeMillis();
        int times1 = binarySearch(dataArray, 2);
        long curTime2 = System.currentTimeMillis();
        int times2 = search(2, dataArray, length);
        int index=firstGreatOrEqual(dataArray,length,2);
        long curTime3 = System.currentTimeMillis();
        System.out.println(times1);
        System.out.println(times2);
        System.out.println(index);
        System.out.println("binarySerach 查询时间：" + (curTime2 - curTime1));
        System.out.println("serach 查询时间：" + (curTime3 - curTime2));
    }

    public static int[] fillArray(int length) {
        int[] dataArray = new int[length];
        //Random random=new Random(length*100);
        for (int i = 0; i < length; i++) {
            dataArray[i] = i * 2;
        }
        return dataArray;
    }

    /**
     * 递归   该方法有很大的问题
     * @param searchData
     * @param dataArray
     * @param length
     * @return
     */
    public static int search(int searchData, int[] dataArray, int length) {
        flagIndex++;
        int[] dataArrays;
        if (searchData == dataArray[length/2]) {
            return flagIndex;
        } else if (length == 1) {
            return -1;
        } else if (searchData > dataArray[length / 2]) {
            dataArrays = Arrays.copyOfRange(dataArray, length / 2, length);
            search(searchData, dataArrays, dataArrays.length);
        } else if (searchData < dataArray[length / 2]) {
            dataArrays = Arrays.copyOf(dataArray, length / 2);
            search(searchData, dataArrays, dataArrays.length);
        }
        return -1;
    }

    /**
     * 原始二分查找算法
     * @param array
     * @param key
     * @return
     */

    public static int binarySearch(int[] array, int key) {
        int left = 0;
        int right = array.length - 1;
        flagIndex++;
        // 这里必须是 <=
        while (left <= right) {
            flagIndex++;
            int mid = (left + right) / 2;
            if (array[mid] == key) {
                return flagIndex;
            } else if (array[mid] < key) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    /**
     * 二分法查找下标
     * @param a
     * @param n
     * @param key
     * @return
     */
    public static int firstGreatOrEqual(int[] a, int n, int key){
        //n + 1 个数
        int low = 0;
        int high = n;
        int mid = 0;
        while(low <= high) {
            mid = low + ((high-low) >> 1);
            if(key <= a[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low <= n ? low : -1;
    }
}
